package org.arithmetic.sort;

import java.util.Collection;

/**
 * Created by LUOLIANG on 2016/8/26.
 * 快速排序
 */
public class QuickSort {
    public static void sort(int numbers[], int lowIndex, int highIndex) {
        int temp, i, j, base;
        if (lowIndex < highIndex) {
            //基准元素设置为第一个
            base = numbers[lowIndex];
            i = lowIndex + 1;
            j = highIndex;

            while (true) {
                while (i < numbers.length && numbers[i] < base) {
                    i++;
                }
                while (j > 0 && numbers[j] > base) {
                    j--;
                }
                if (i >= j)
                    break;
                temp = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = temp;
            }
            numbers[lowIndex] = numbers[j];
            numbers[j] = base;
            sort(numbers, lowIndex, j - 1);
            sort(numbers, j + 1, highIndex);
        }
    }


    public static void main(String[] args) {
        int numbers[] = {23, 45, 2, 4, 1, 34, 9, 8, 456, 99};

        System.out.println("排序之前：");
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }

        sort(numbers, 0, numbers.length - 1);

        System.out.println("\n排序之后：");
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
    }

}
